import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/15
 * \* Time: 23:05
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class N皇后 {
    /**
     * 结果集
     */
    List<List<String>> res=new LinkedList<>();

    /**
     * 主函数
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        ArrayList<StringBuilder> track=new ArrayList<>();
        //初始化棋盘
        for(int i=0;i<n;i++){
            StringBuilder str = new StringBuilder();
            for(int j = 0; j < n; j++){
                str.append('.');
            }
            track.add(new StringBuilder(str));
        }
        backtrace(track,0);
        return res;
    }

    void backtrace(ArrayList<StringBuilder> track, int row){
        //结束条件，每一行都成功放置皇后
        if(row== track.size()){
            ArrayList<String> track1 = new ArrayList<>();
            //将StringBuilder类转化为String类
            for(int i = 0; i < track.size(); i++){
                track1.add(track.get(i).toString());
            }
            res.add(track1);
            return;
        }

        int n=track.get(row).length();
        for(int col=0;col<n;col++){
            if(!isValid(track,row,col)){
                continue;
            }
            //做选择
            track.get(row).setCharAt(col,'Q');
            //进入下一轮放置皇后
            backtrace(track,row+1);
            //撤销选择
            track.get(row).setCharAt(col,'.');
        }
    }

    boolean isValid(ArrayList<StringBuilder> track,int row,int col){
        int n=track.size();
        // 检查列是否有皇后冲突
        for(int i = 0; i < n; i++){
            if(track.get(i).charAt(col) == 'Q'){
                return false;
            }
        }
        // 检查右上方是否有皇后冲突
        for(int i = row-1, j = col+1; i>=0 && j <n; i--,j++){
            if(track.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        // 检查左上方是否有皇后冲突
        for(int i= row-1, j = col-1; i>=0 && j >=0; i--,j--){
            if(track.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        return true;
    }
}